package tree.structure.huffman;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author: 26233
 * @create: 2022-07-25 15:26:13
 * @Description
 *
 * 哈夫曼树
 *  1. WPL最优的二叉树。
 *  2. WPL: sum(叶子结点权重 * 叶子节点到根节点路径长)
 *  3. 构造方法：
 *      a. W(w1, w2, w3, w4, ...) 权重的集合
 *      b. 选取W中最小的两个wi，wj组成一颗二叉树,根节点权重为wi + wj, 再加入W集合中wij，并删除原来的wi，wj
 *      c. 重复b的操作，直到W中只剩下一个节点
 **/

public class HuffmanTree {

    private HuffmanTreeNode root;
    private int wpl;

    public HuffmanTreeNode genHuffmanTree(List<HuffmanTreeNode> nodes){
        while(nodes.size() > 1) {
            nodes = mergeSortedNodes(nodes);
        }
        root = nodes.get(0);

        return root;
    }

    public HuffmanTreeNode getRoot() {
        return root;
    }

    public int getWpl() {
        return wpl;
    }

    public List<HuffmanTreeNode> mergeSortedNodes(List<HuffmanTreeNode> nodes){
        if (nodes.size() > 1) {
            HuffmanTreeNode left = nodes.remove(0);
            HuffmanTreeNode right = nodes.remove(0);

            HuffmanTreeNode newNode = HuffmanTreeNode.genNode(left, right);
            insertToNodes(nodes, newNode);

            wpl += newNode.getWeight();
        }

        return nodes;
    }

    public void insertToNodes(List<HuffmanTreeNode> nodes, HuffmanTreeNode newNode){
        nodes.add(newNode);
        nodes.sort(Comparator.comparingInt(HuffmanTreeNode::getWeight));
    }

    public static void main(String[] args) {

        int[] weights = new int[]{2, 3, 6, 7, 10, 19, 21, 32};
        List<HuffmanTreeNode> collect =
                Arrays.stream(weights)
                        .mapToObj(HuffmanTreeNode::genNode)
                        .sorted(Comparator.comparingInt(HuffmanTreeNode::getWeight))
                        .collect(Collectors.toList());
        System.out.println("collect = " + collect);


        HuffmanTree huffmanTree = new HuffmanTree();
        HuffmanTreeNode root = huffmanTree.genHuffmanTree(collect);

        System.out.println("huffmanTreeNode = " + root);
        System.out.println("wpl = " + huffmanTree.getWpl());

    }

}
